package app;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * User: admin
 * Date: 15.05.14
 * Time: 19:25
 * To change this template use File | Settings | File Templates.
 */
public class Tst_class {
    //Parameters definition
    private static int[] input_arr;

    public static void main(String[] args) {
        bin_search1(input_arr = new int[]{1,65,-7,0,3,2,12,193,-54,11,17});
        bin_search2(input_arr = new int[]{1,65,-7,0,3,2,12,193,-54,11,17});
    }

    public static void bin_search1(int[] arr){
        System.out.println("----- Arrays.sort + Arrays.binarySearch -----");
        System.out.println("Input array: " + Arrays.toString(arr));
        Arrays.sort(arr);   // prepare array for a binary search
        System.out.println("Sorted array: " + Arrays.toString(arr));
        int key, i;
        key = arr[0];   // identify key for a binary search
        System.out.println("Element to search: " + key);
        i = Arrays.binarySearch(arr, key);
        System.out.println("Index of '" + key + "': " + i);
    }

    public static void bin_search2(int[] arr){
        System.out.println("----- Arrays.sort + Recursive binary search -----");
        System.out.println("Input array: " + Arrays.toString(arr));
        Arrays.sort(arr);   // prepare array for a binary search
        System.out.println("Sorted array: " + Arrays.toString(arr));
        int key, i;
        key = arr[0];   // identify key for a binary search
        System.out.println("Element to search: " + key);
        i = binary_search(arr, key, 0, arr.length-1);   //perform a binary search
        System.out.println("Index of '" + key + "': " + i);
    }

    public static int binary_search(int[] arr, int key, int ilow, int ihigh) {
        int mid;
        if (ihigh < ilow)   //key is not found
            return -1;
        mid = (ilow + ihigh)/2;
        if (key == arr[mid])
            return mid;
        else if (key < arr[mid])
            return binary_search(arr, key, ilow, mid-1);
        else if (key > arr[mid])
            return binary_search(arr, key, mid+1, ihigh);
        return -2;
    }

    public void bin_to_dec() {
        String str = "111";
        Integer decnum = Integer.parseInt(str, 2);
        System.out.println(str + " -> " + decnum);
    }

    public static void fibonacci () {
        {
            String inputString = "0ab5c1120 2$#";
            System.out.println("Input string is: \"" + inputString + "\"");
            String digitStr = "";
            String charStr = "";
            List<Integer> digits = new ArrayList<Integer>();
            List<Integer> fib_digits = new ArrayList<Integer>();
//find digits in the input string
            for (int i = 0; i < inputString.length(); i++) {
                if (Character.isDigit(inputString.charAt(i))) {
                    digitStr += inputString.charAt(i);
                } else {
                    //combining digits array
                    if (!digitStr.isEmpty()) {
                        digits.add(Integer.parseInt(digitStr));
                        digitStr = "";
                    }
                    //combining string without digits
                    charStr += inputString.charAt(i);
                }
            }
            if (!digitStr.isEmpty()) {
                digits.add(Integer.parseInt(digitStr));
                digitStr = "";
            }
            System.out.print("Numbers are: ");
            for (Integer i : digits) {
                System.out.print(i + ", ");
            }
            System.out.println();
//find fibonacci numbers within the digits array
            for (Integer i : digits) {
                if (ehFibonacci(i)) {
                    fib_digits.add(i);
                }
            }
            System.out.print("Fibonacci numbers are: ");
            for (Integer i : fib_digits) {
                System.out.print(i + ", ");
            }
            System.out.println();

//cut digits from input string
            System.out.println("Input string without digits: \"" + charStr + "\"");

        }
    }
//aux find fibonacci numbers
    public static boolean ehFibonacci(int n) {
        int fib1 = 0;
        int fib2 = 1;
        do {
            int saveFib1 = fib1;
            fib1 = fib2;
            fib2 = saveFib1 + fib2;
        }
        while (fib2 < n);

        if (fib2 == n)
            return true;
        else
            return false;

    }

 }


